package dp;

/**
 * @author tmh
 * @date 2024/9/14 21:45
 * @description 五部曲
 * 确定dp[i]含义，dp[i]：第i个斐波拉契数列的值为dp[i]
 * 递推公式
 * dp数组如何初始化
 * 遍历顺序：从前向后遍历
 * 打印dp数组
 */
public class T509斐波那契数 {
    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0]=0;
        dp[1]=1;
        for (int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
